\graphicspath{{./figures/background/}}



\chapter{Antecedentes}
\label{chap:background}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Optimización Global}
\label{sec:optimizacion}

% Una definición para el término \textit{optimización} sería la siguiente \cite{Rao96}: \textit{``Optimización es el acto de obtener los mejores resultados bajo determinadas circunstancias''}.

El método para buscar el óptimo global (que puede no ser único) de alguna función se conoce como \textit{Optimización Global} \cite{Coello07}. 

La optimización puede definirse como el problema de encontrar un \textit{vector de variables de decisión} tal que maximice la satisfacción de una \textit{función objetivo} cumpliendo con una serie de restricciones. Antes de plantear formalmente esta definición es necesario presentar algunos conceptos importantes.

\begin{mydef}\textnormal{
\textbf{(Vector de diseño o vector de variables de decisión):} Las variables de decisión son los parámetros que deben ajustarse para dar solución a un problema de optimización. Un vector de variables de decisión se puede representar de la siguiente manera:
\begin{eqnarray} 
 \mathbf{X} &=& \left[ 
\begin{array}{c}
x_1 \\
x_2 \\
\vdots\\[-0.25cm]
x_n
\end{array}
\right]  
\end{eqnarray}
donde $x_i$ denota la $i$-ésima de $n$ variables de decisión. Para este trabajo se utilizará por conveniencia la siguiente representación: 
\begin{eqnarray} 
 \mathbf{X} &=& [x_1, x_2, \dots, x_n]^T
\end{eqnarray}
}\end{mydef}

\begin{mydef}\textnormal{
\textbf{(Restricciones):} Criterios o requerimientos que una solución debe satisfacer para ser considera una solución factible. De otro modo, cuando una solución no satisface todas las restricciones del problema se considera una solución infactible. Las restricciones pueden ser de desigualdad (Ecuación (\ref{eq:desigualdad})) o de igualdad (Ecuación (\ref{eq:igualdad})):
\begin{eqnarray}
g_{i}(\mathbf{X})  & \leq & 0 \ \ \ \ \ \ i = 1, 2, \dots , m  \label{eq:desigualdad}\\
h_{j}(\mathbf{X})  & =    & 0 \ \ \ \ \ \ j = 1, 2, \dots , p \label{eq:igualdad}
\end{eqnarray}
}\end{mydef}

\begin{mydef}\textnormal{
\textbf{(Función objetivo):} Es un criterio expresado en función de las variables de decisión  y se utiliza para medir la calidad de las diferentes alternativas de solución para determinado problema de optimización. Una función objetivo será representada en este trabajo de tesis como $f(\mathbf{X})$, donde $f: \mathbb{R}^n \rightarrow \mathbb{R}$ y $\mathbf{X}$ es un vector de variables de decisión.
}\end{mydef}


\begin{mydef}\textnormal{
\textbf{(Espacio de búsqueda):} El espacio de búsqueda ($\mathcal{U}$) corresponde a todo el universo de soluciones candidatas al problema.
}\end{mydef}

\begin{mydef}\textnormal{
\textbf{(Región factible):} La región factible ($\mathcal{F}$) es el subconjunto de todas las posibles soluciones que satisfacen las restricciones de desigualdad $g(\mathbf{X})$  y las restricciones de igualdad $h(\mathbf{X})$ descritas en las Ecuaciones (\ref{eq:desigualdad}) y (\ref{eq:igualdad}), respectivamente. Formalmente:
\begin{eqnarray} 
\mathcal{F} &  = & \{\mathbf{X} \in \mathcal{U} : g(\mathbf{X})\leq 0 \wedge h(\mathbf{X})=0\}
\end{eqnarray}
}\end{mydef}


Una vez planteados los conceptos anteriores, la optimización puede definirse formalmente como el problema de encontrar el vector $\mathbf{X}^* =  [x_{1}^*, x_{2}^*, \dots , x_{n}^*]^{T}$ que satisfaga las $m$ restricciones de desigualdad:
\begin{equation} \label{eq:moodesigualdad}
 g_{i}(\mathbf{X})  \leq 0 \ \ \ \ \ \ i = 1, 2, \dots , m
\end{equation}
las $p$ restricciones de igualdad:
\begin{equation} \label{eq:mooigualdad}
 h_{j}(\mathbf{X})  = 0 \ \ \ \ \ \ j = 1, 2, \dots , p
\end{equation}
y que minimice\footnote{Sin pérdida de generalización, en este documento haremos referencia únicamente a problemas de minimización.} la función:
\begin{equation}
f(\mathbf{X})
\end{equation}
donde  $\mathbf{X}$ es un vector de variables de decisión, $f(\mathbf{X})$ es la función objetivo.

% Una vez planteados los conceptos anteriores, la optimización puede definirse formalmente como el problema de encontrar manera:
% \begin{eqnarray} 
% \mbox{Encontrar} & \mathbf{X} = [x_1, x_2, \dots, x_n]^T & \mbox{que minimice } f(\mathbf{X})\nonumber
% \end{eqnarray}
% sujeto a las restricciones:
% \begin{eqnarray} 
% & \begin{array}{rl}
% g_i(\mathbf{X}) \leq 0 & i= 1,2,\dots, m \\ \nonumber
% h_j(\mathbf{X}) = 0 & j= 1,2,\dots, p 
% \end{array} &\label{eq:problem}
% \end{eqnarray}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Optimización Multiobjetivo}
\label{sec:moo}

Osyczka define la optimización multiobjetivo (también conocida como optimización multicriterio u optimización vectorial) de la siguiente manera \cite{Osyczka84}:

\begin{quote}
 \textit{``El problema de encontrar un vector de variables de decisión que satisfaga las restricciones y optimice una función vectorial cuyos elementos representen las funciones objetivo. Estas funciones forman una descripción matemática de los criterios de desempeño que usualmente están en conflicto entre sí. Por lo tanto, el término ``optimizar'' significa encontrar una solución tal que proporcione valores para todos los objetivos que resulten aceptables para el tomador de decisiones.''}
\end{quote}


\begin{mydef}\textnormal{
\textbf{(Función vectorial o vector de funciones objetivo):} Cuando se optimizan múltiples objetivos las $M \geq 2$ funciones objetivos pueden representarse mediante un vector de la siguiente manera:
\textnormal{
\begin{eqnarray} 
 \mathbf{F}(\mathbf{X})  &=& \left[ 
\begin{array}{c}
f_{1}(\mathbf{X}) \\
f_{2}(\mathbf{X}) \\
\vdots\\[-0.25cm]
f_{M}(\mathbf{X})
\end{array}
\right]  
\end{eqnarray}}
donde $f_{m}(\mathbf{X})$ denota la $m$-ésima función objetivo. Por conveniencia se utilizará la siguiente representación: 
\textnormal{
\begin{equation}
 \mathbf{F}(\mathbf{X}) =  [f_{1}(\mathbf{X}), f_{2}(\mathbf{X}), \dots , f_{M}(\mathbf{X})]^{T}
\end{equation}}
}\end{mydef}

Formalmente, la optimización multiobjetivo se puede definir como el problema de encontrar el vector $\mathbf{X}^* =  [x_{1}^*, x_{2}^*, \dots , x_{n}^*]^{T}$ que satisfaga las $m$ restricciones de desigualdad:
\begin{equation} \label{eq:moodesigualdad}
 g_{i}(\mathbf{X})  \leq 0 \ \ \ \ \ \ i = 1, 2, \dots , m
\end{equation}
las $p$ restricciones de igualdad:
\begin{equation} \label{eq:mooigualdad}
 h_{j}(\mathbf{X})  = 0 \ \ \ \ \ \ j = 1, 2, \dots , p
\end{equation}
y que optimice la función vectorial:
\begin{equation}
 \mathbf{F}(\mathbf{X}) =  [f_{1}(\mathbf{X}), f_{2}(\mathbf{X}), \dots , f_{M}(\mathbf{X})]^{T}
\end{equation}

donde $\mathbf{X} =  [x_{1}, x_{2}, \dots , x_{n}]^{T}$ es el vector de $n$ variables de decisión, y $M$ es el número de funciones objetivo ($M \geq 2$). En otras palabras, deseamos determinar de entre el conjunto $\mathcal F$ de todos los valores que satisfacen (\ref{eq:moodesigualdad}) y (\ref{eq:mooigualdad}) al conjunto $x_{1}^{*}, x_{2}^{*}, \dots , x_{n}^{*}$ que aporte los valores óptimos para todas las funciones objetivo.

La noción de optimalidad es diferente en optimización multiobjetivo, ya que por lo general no existe una única solución que pueda ser considerada óptima. Por el contrario, se pretende encontrar  los mejores compromisos posibles entre los objetivos. La noción de optimalidad generalmente adoptada es la de \textit{óptimo de Edgeworth-Pareto}, u \textit{óptimo de Pareto} como es más comúnmente conocida \cite{pareto1896cours}. Esta noción de optimalidad se presenta a continuación.



\begin{mydef}\textnormal{
\textbf{(Dominancia de Pareto):} Dadas dos soluciones $\mathbf{X}_{i}$, $\mathbf{X}_{j}$ $\in$ $\mathcal{F}$, decimos que $\mathbf{X}_{i}$ domina a $\mathbf{X}_{j}$ de acuerdo con la dominancia de Pareto ($\mathbf{X}_{i}$ $\prec_{P} $ $\mathbf{X}_{j}$) si y sólo si:
\begin{eqnarray}
&& \forall{m \in \{1, 2, ..., M\}} : f_{m}(\mathbf{X}_{i}) \leq f_{m}(\mathbf{X}_{j}) \;\;\wedge\nonumber \\ 
&& \exists{m \in \{1, 2, ..., M\}} : f_{m}(\mathbf{X}_{i}) < f_{m}(\mathbf{X}_{j}) 
\end{eqnarray}
De otro modo, decimos que $\mathbf{X}_{j}$ es una solución no dominada con respecto a $\mathbf{X}_{i}$.
}\end{mydef}


\begin{mydef}\textnormal{\label{def:optimopareto}
\textbf{(Óptimo de Pareto):} Un vector solución es considerado \textit{óptimo de Pareto} si no existe otro vector factible que mejore la satisfacción de alguno de los objetivos sin provocar simultáneamente un deterioro en algún otro criterio. Más formalmente, un vector de variables de decisión $\mathbf{X}^* \in \mathcal F$ es un óptimo de Pareto si no existe otro vector $\mathbf{X} \in \mathcal F$ tal que $\mathbf{X}$ domine a $\mathbf{X}^*$ de acuerdo con la dominancia de Pareto ($\mathbf{X} \prec_{P} \mathbf{X}^*$).
}\end{mydef}

\begin{mydef}\textnormal{
\textbf{(Conjunto de óptimos de Pareto):} El conjunto de óptimos de Pareto \textnormal{PS}$^*$ es un conjunto de puntos en el espacio de las variables de decisión que poseen las características descritas en el Concepto \ref{def:optimopareto}. Formalmente:
\begin{eqnarray}
\mbox{PS}^* & = & \{\mathbf{X}^* \in \mathcal{F} : \neg\exists \mathbf{X}\in \mathcal{F} : \mathbf{X} \prec_{P} \mathbf{X}^*\}
\end{eqnarray}
}\end{mydef}



\begin{mydef}\textnormal{
\textbf{(Frente de Pareto o superficie compromiso):} El conjunto de óptimos de Pareto representado en el espacio de las funciones objetivo constituye lo que se conoce como superficie compromiso o frente de Pareto (\textnormal{FP}):
\begin{eqnarray}
\mbox{FP} & = & \{ \mathbf{F}(\mathbf{X}^*) : \mathbf{X}^* \in \mbox{PS}^*\}
\end{eqnarray}
}\end{mydef}


Los conceptos y definiciones anteriores constituyen el dominio de los problemas de optimización multiobjetivo y pueden visualizarse en la figura \ref{fig:dominio}.
\begin{figure}[htp]
  \centering
\shadowbox{
\includegraphics{emoo.pdf}
}
\caption{Dominio de los problemas de optimización multiobjetivo.}\label{fig:dominio}
\end{figure}


Existen distintos aspectos importantes al optimizar múltiples objetivos, pero antes es necesario introducir algunos conceptos.


\begin{mydef}\textnormal{
\textbf{(Conjunto aproximación):} Los optimizadores multiobjetivo por lo general intentan encontrar una aproximación al frente de Pareto (PF) para determinado problema. En este trabajo por conjunto aproximación ($Z$) nos referiremos al conjunto de vectores de objetivos no dominados encontrados por un optimizador multiobjetivo.
}\end{mydef}

\begin{mydef}\textnormal{
\textbf{(Tomador de decisiones):} Como ya se mencionó en la Sección \ref{sec:moo}, resolver un problema de optimización multiobjetivo consiste en encontrar un conjunto de soluciones compromiso, el cual puede contener un número infinito de alternativas. Sin embargo, generalmente se tendrá que elegir una de esas soluciones como curso de acción para hacer frente a dicho problema. Todas las soluciones que cumplen con las características de un óptimo de Pareto son matemáticamente equivalentes, por lo que elegir alguna de las alternativas requiere de información que no está contenida en las funciones objetivo. En este sentido, el tomador de decisiones es la persona (o conjunto de personas) que se asume tendrá(n) un amplio conocimiento del problema y que expresará(n) relaciones de preferencia entre las diferentes soluciones para tomar una decisión final \cite{Miettinen94}.
}\end{mydef}

De acuerdo con Purshouse \cite{Purshouse03c}, la tarea de un optimizador multiobjetivo es proveer una representación precisa y útil de la superficie compromiso para el tomador de decisiones. Así mismo, Purshouse destacó tres aspectos que se buscan para determinar la calidad del conjunto aproximación $Z$ obtenido por un optimizador multiobjetivo \cite{Purshouse03c}:

\begin{itemize}
\item \textbf{Proximidad (convergencia):}  El conjunto $Z$ debe tener soluciones cuyos vectores de objetivos correspondientes sean cercanos al frente de Pareto.
\item \textbf{Diversidad:}  El conjunto $Z$ debe contener una buena distribución de las soluciones, tanto en términos de extensión como de uniformidad. Una buena diversidad es comúnmente de interés en el espacio de objetivos, pero puede requerirse también en el espacio de las variables de decisión. 
\item \textbf{Pertinencia:}  El conjunto $Z$ debe contener únicamente soluciones que se encuentren en la región de interés del tomador de decisiones. En la práctica, y especialmente al incrementarse la cantidad de objetivos, el tomador de decisiones estará interesado sólo en una sub-región del espacio de objetivos.
\end{itemize}
% 
% 
% 
%    • Proximity. The approximation set should contain solutions whose corresponding ob-
%       jective vectors are close to the true Pareto front.
%    • Diversity. The approximation set should contain a good distribution of solutions,
%       in terms of both extent and uniformity. Good diversity is commonly of interest in
%       objective-space, but may also be required in decision-space. In objective-space, the
%       approximation set should extend across the entire range of the true Pareto front with
%       a parametrically uniform distribution across the surface.
%    • Pertinency. The approximation set should only contain solutions in the decision-
%       maker region of interest (ROI). In practice, and especially as the number of objectives
%       increases, the DM is interested only in a sub-region of objective-space. Thus, there
%       is little benefit in representing trade-off regions that lie outside the ROI. Focusing on
%       pertinent areas of the search space helps to improve optimiser efficiency and reduces
%       unnecessary information that the DM would otherwise have to consider.


% Para este trabajo se asume que los distintos objetivos de un problema de optimización son igualmente importantes. Así mismo, se asume que el tomador de decisiones estará interesado en en todo el frente de Pareto y no en una región específica de éste.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Algoritmos Evolutivos}
\label{sec:evolutionary}

\subsection{Inspiración biológica}

% La naturaleza esta llena de comportamientos extraordinarios que han sido fuente de inspiración para el desarrollo de una amplia variedad de algoritmos computacionales. 
La naturaleza ha sido fuente inagotable de inspiración para el desarrollo de una amplia variedad de algoritmos computacionales. Los Algoritmos Evolutivos (AEs) engloban un conjunto de técnicas que toman inspiración y simulan el proceso natural de la evolución. Más específicamente, los AEs se inspiran en la teoría evolutiva más aceptada actualmente: el \textit{Neo-Darwinismo}\footnote{El paradigma Neo-Darwiniano es el resultado de la combinación de la teoría evolutiva de Darwin, el seleccionismo de Weismann y la genética de Mendel.}.  El Neo-Darwinismo establece que la vida puede explicarse como la ocurrencia repetida de distintos procesos estadísticos que interactúan entre sí sobre las poblaciones:
\begin{itemize}
\item \textbf{Reproducción}: Combinación de individuos y transferencia del código genético a su descendencia.
\item \textbf{Mutación}: Errores en la transferencia de información genética durante la reproducción. Es un aspecto necesario para incluir variabilidad en las especies.
\item \textbf{Competencia}: Consecuencia del crecimiento de la población en un entorno con recursos limitados.
\item \textbf{Selección}: Los individuos mejor adaptados tendrán mayor oportunidad de sobrevivir y reproducirse.
\end{itemize}

La evolución por sí misma puede ser vista como un proceso de optimización, donde las diferentes especies tienen que mejorar constantemente para adaptarse y competir en su entorno. 





\subsection{Algoritmo Evolutivo Generalizado}
\label{sec:generalizedea}

El término algoritmo evolutivo (AE) es generalmente utilizado para describir cualquier método de búsqueda estocástico basado en poblaciones. La idea fundamental de los AEs es evolucionar progresivamente una población de individuos (soluciones potenciales para el problema de optimización) a través de la aplicación iterativa de procesos probabilísticos de variación y selección hasta que algún criterio de terminación sea alcanzado (por lo regular un número máximo de iteraciones (generaciones)). Para simular el proceso evolutivo se requiere:
\begin{itemize}
\item \textbf{Representación}: una forma de codificar las soluciones candidatas para un problema dado.
\item \textbf{Operadores de variación}: operadores que permitan la generación de nuevos individuos a partir de los ya existentes. 
\item \textbf{Función de aptitud}: una función que permita expresar la calidad de las soluciones candidatas. 
\item \textbf{Mecanismo de selección}: estrategia para seleccionar los individuos que podrán reproducirse de acuerdo con su aptitud.
\end{itemize}

 Existen tres paradigmas principales: la Programación Evolutiva (\textit{Evolutionary Programming}, EP) propuesta por Fogel \cite{fogel1966}, los Algoritmos Genéticos (\textit{Genetic Algorithms}, GA) propuestos por Holland  \cite{Holland73} y las Estrategias Evolutivas (\textit{Evolution Strategies}, ES)  propuestos por Rechenberg \cite{Rechenberg73}. La principal diferencia entre estos paradigmas radica en la representación que utilizan para codificar las alternativas de solución y en los operadores de variación incorporados.


Purshouse describe la estructura general de un AE mediante la Ecuación \ref{eq:ea} \cite{Purshouse03c}:
\begin{eqnarray}\label{eq:ea}
P_{t+1} & = & S_s(V(S_v(P_t)), P_t)
\end{eqnarray}
donde $P_t$ denota la población en el tiempo $t$ (generación actual) y, por lo tanto, $P_{t+1}$ representa la población para la siguiente generación. $V$ es una función que representa los operadores de variación incorporados y las funciones $S_v$ y $S_s$ denotan los mecanismos de selección para variación (\textit{selection-for-variation}) y selección para supervivencia (\textit{selection-for-survival}), respectivamente. Estos tres últimos elementos serán descritos por separado a continuación:

\begin{itemize}
\item \textbf{Selección para variación (\textit{selection-for-variation}), $S_v$:} Esta función se refiere a la etapa donde se seleccionan los individuos de $P_t$ sobre los que se aplicarán los operadores de variación $V$. Para este proceso de selección se tomará en cuenta el valor de aptitud de las soluciones, de manera que los mejores individuos en la población generalmente tendrán una mayor oportunidad de reproducirse. Se asume que a partir de buenas soluciones es posible generar nuevas buenas soluciones.
\item \textbf{Operadores de variación, $V$:} Los operadores de variación son los encargados de generar nuevos individuos a partir de los ya existentes. Estos operadores se clasifican de acuerdo con el número de \textit{individuos padre} que se utilizan para generar nuevos \textit{individuos hijo}. Cuando se utiliza un solo padre el proceso de variación se conoce usualmente como \textit{mutación}, mientras que la combinación de múltiples padres se conoce generalmente como \textit{cruza} o \textit{recombinación}. Cada operador de variación tiene una probabilidad de aplicación asociada dependiendo del problema en cuestión.
\item \textbf{Selección para supervivencia (\textit{selection-for-survival}), $S_s$:} Una vez aplicados los operadores de variación se tienen dos conjuntos de soluciones: $P_t$ que denota la población original y $V(S_v(P_t))$ que está formada por los individuos creados como consecuencia de los operadores de variación. Los AEs trabajan con poblaciones de tamaño finito $N$, por lo que en esta etapa son seleccionados los $N$ individuos que sobrevivirán y formarán la población de padres para la siguiente generación.
\end{itemize}


\subsection{Algoritmos Evolutivos para Optimización Multiobjetivo}
\label{sec:moeas}

Tal como se mencionó en las secciones anteriores, al optimizar múltiples objetivos estamos interesados en encontrar un conjunto de soluciones compromiso que aproximen de manera representativa el frente de Pareto. Dado este requerimiento, los AEs son una alternativa particularmente apropiada para resolver problemas multiobjetivo. Los AEs trabajan simultáneamente con una población de soluciones candidatas que les permite encontrar diferentes miembros del conjunto de óptimos de Pareto en una sola ejecución, en contraste con los enfoques tradicionales y algunos otras heurísticas que para lograrlo requieren llevar a cabo una serie de ejecuciones independientes. El uso de poblaciones también permite que los AEs exploren distintas regiones del espacio de búsqueda a la vez, con lo que evitan quedar atrapados en óptimos locales. Adicionalmente, la flexibilidad de los AEs los hace menos susceptibles a la forma y continuidad de la superficie compromiso, ya que pueden lidiar con frentes de Pareto desconectados y cóncavos.

En los 1960s, Rosenberg \cite{Rosenberg67} estableció los primeros indicios de la utilización de algoritmos evolutivos para optimizar problemas multiobjetivo. Sin embargo, el problema con el cual trabajaba fue replanteado considerando un único objetivo. Fue hasta mediados de los 1980s cuando Schaffer realizara la primera implementación de un algoritmo evolutivo multiobjetivo (MOEA): el \textit{Vector Evaluated Genetic Algorithm} (VEGA) \cite{Schaffer85}. 

 
En los 1990s el área de la optimización evolutiva multiobjetivo se afianzó y surgieron diversos enfoques importantes: el \textit{Multi-Objective Genetic Algorithm} (MOGA) propuesto por Fonseca y Fleming \cite{Fonseca93}; el \textit{Niched Pareto Genetic Algorithm} (NPGA) propuesto por Horn y Nafpliotis \cite{Horn93}; el \textit{Nondominated Sorting Genetic Algorithm} (NSGA) propuesto por Srinivas y Deb \cite{Srinivas94}; y enfoques como el \textit{Strength Pareto Evolutionary Algorithm} (SPEA) de Zitzler y Thiele \cite{Zitzler99c} y el \textit{Pareto Archived Evolution Strategy} (PEAS) de Knowles y Corne \cite{Knowles99} que popularizaron el uso de elitismo en MOEAs.

Posteriormente, comenzó a surgir una nueva generación de MOEAs que incorporaron mecanismos más eficientes y sofisticados para mejorar la convergencia y/o preservación de diversidad. En esta nueva generación de MOEAs podemos destacar el \textit{Elitist Non-Dominated Sorting Genetic Algorithm} (NSGA-II) propuesto por Deb \textit{\textit{et al.}} \cite{Deb00f,Deb02}, que se ha convertido en el MOEA más representativo de la literatura y ha sido utilizado ampliamente como punto de referencia para nuevos desarrollos; el \textit{Pareto Envelope-based Selection Algorithm} (PESA) propuesto por Corne \textit{\textit{et al.}} \cite{Corne00} para incorporar ideas de SPEA y PAES, su nueva versión PESA-II \cite{Corne01} cuyo mecanismo de selección está basado en regiones; y SPEA2 de Zitzler \textit{\textit{et al.}} \cite{Zitzler01} que presenta un mecanismo de estimación de la densidad y un esquema mejorado y más estricto de asignación de aptitud. 

Coello \textit{\textit{et al.}} \cite{Coello07} proporcionan un descripción más completa de cada uno de los enfoques citados.


% \subsection{Aspectos importantes al diseñar MOEAs}
% \label{sec:keyissuesmoeas}
% 
% En esta sección se describen tres aspectos de gran importancia que deben ser tomados en cuenta al diseñar MOEAs: la \textit{asignación de aptitud}, la \textit{preservación de diversidad}, y el \textit{elitismo}.
% 
% 
% \subsubsection{Asignación de aptitud} 
% 
% 
% % it is imperative to implement a function which measures the 
% % fitness of the individuals, such that the emulation can favour those individuals 
% % that compete most effectively for resources. Usually, when dealing with a 
% % single-objective optimization problem such fitness function is directly 
% % related to the function to be optimized. However, when the problems involve 
% % the simultaneous satisfaction of two or more objectives (the so-called 
% % ``multiobjective optimization problems'', or MOP for short), such relation 
% % is not straightforward, since it is required an additional mechanism to map 
% % the multiobjective space into a single dimension in order to allow a direct 
% % comparison among solutions; this mechanism is known as the \textit{fitness assignment 
% % process\footnote{In this study, we will use indistinctly the terms fitness 
% % and  rank to refer to the value which expresses the quality of solutions 
% % and which allows to compare them with respect to each other.}} \cite{Hughes08}
% 
% 
% \subsubsection{Preservación de diversidad}
% \subsubsection{Elitismo}



\section{Optimización de muchos objetivos}
\label{sec:manyobjective}

\subsection{Introducción}
\label{sec:intromany}

A lo largo de la historia se han reportado diversos MOEAs (ver Sección \ref{sec:moeas}), muchos de los cuales han demostrado ser competitivos al optimizar problemas con 2 o 3 objetivos manteniendo un número relativamente bajo de evaluaciones. Sin embargo, recientemente se ha reportado que el desempeño de la mayoría de estos enfoques se degrada significativamente con el aumento en el número de objetivos a optimizar \cite{Purshouse03b,Khare03,Hughes05,Praditwong07,Knowles07,Ishibuchi08e}. Tal es la problemática, que se propuso el término \textit{Many-Objective} para referirse al subconjunto de problemas donde muchos (más de tres) objetivos requieren ser optimizados \cite{Farina02b}, término que se popularizó y se ha seguido utilizando en la literatura especializada. 

La alta dimensionalidad del espacio de objetivos conlleva una amplia problemática \cite{Corne07,Ishibuchi08e}:
\begin{itemize}
\item Proporción de soluciones no dominadas. Al ser incrementada la cantidad de objetivos, la población se satura rápidamente de soluciones no dominadas, provocando el deterioro de la habilidad de búsqueda de MOEAs (ver Sección \ref{sec:paretodrawbacks}).
\item Crecimiento exponencial en el número de soluciones requeridas para aproximar representativamente el frente de Pareto. 
\item Algunos MOEAs se basan en estructuras de datos y subrutinas cuyas demandas computacionales crecen exponencialmente (en espacio y tiempo, respectivamente) con el número de objetivos.
\item Dificultad en la visualización de las soluciones. 
\end{itemize}


\subsection{Inconvenientes de la dominancia de Pareto}
\label{sec:paretodrawbacks}

El incremento en la cantidad de objetivos afecta principalmente a los enfoques que utilizan la dominancia de Pareto (PD) como criterio para discriminar entre soluciones y guiar el proceso de búsqueda (la gran mayoría de los MOEAs existentes se basan en este concepto). Esto se debe a que la proporción de soluciones no dominadas en la población se incrementa de manera drástica con el número de objetivos. Con el propósito de aclarar este punto, la figura \ref{fig:nondominated} muestra cómo se comporta el porcentaje de soluciones no dominadas en la población de un MOEA en relación con el número de objetivos al avanzar el proceso de búsqueda. El MOEA utilizado se describe en la Sección \ref{sec:MOEA}. Para este experimento se utilizaron seis problemas de prueba escalables (DTLZ1-DTLZ6), que serán descritos en la Sección \ref{sec:dtlz}, y se utilizaron instancias con $M=\{5,10,15,20,30,50\}$ objetivos. Los datos graficados en la figura \ref{fig:nondominated} corresponden a la media de 31 repeticiones independientes para cada configuración del experimento.


\begin{figure}[htp]
  \centering
\subfigure[DTLZ1.]{
\includegraphics[width=8cm]{DTLZ1_nondominated_mean.pdf}
}
\subfigure[DTLZ2.]{
\includegraphics[width=8cm]{DTLZ2_nondominated_mean.pdf}
}
\subfigure[DTLZ3.]{
\includegraphics[width=8cm]{DTLZ3_nondominated_mean.pdf}
}
\subfigure[DTLZ4.]{
\includegraphics[width=8cm]{DTLZ4_nondominated_mean.pdf}
}
\subfigure[DTLZ5.]{
\includegraphics[width=8cm]{DTLZ5_nondominated_mean.pdf}
}
\subfigure[DTLZ6.]{
\includegraphics[width=8cm]{DTLZ6_nondominated_mean.pdf}
}
\caption{Proporción de soluciones no dominadas en relación con el número de objetivos.} \label{fig:nondominated}
\end{figure}

A partir de la figura \ref{fig:nondominated} es posible observar que el aumento en el número de objetivos claramente provoca un incremento en el porcentaje de soluciones no dominadas en la población en los seis casos de prueba considerados. Este problema se acentúa rápidamente con el avance del proceso de búsqueda, de manera que en las primeras generaciones la población se satura por completo de soluciones no dominadas. Es importante notar que incluso desde la población inicial (generación 0), que es generada aleatoriamente, un alto porcentaje de la población corresponde a soluciones no dominadas, especialmente para los problemas DTLZ4 y DTLZ6. Cuando todas las soluciones en la población son no dominadas (\textit{v.g.}, equivalentes de acuerdo con la dominancia de Pareto) no es posible discriminar entre ellas, de manera que el proceso de selección y, por lo tanto, el proceso de guiar la búsqueda se llevan a cabo prácticamente de manera aleatoria.

En realidad, PD sólo es apropiada para problemas con pocos objetivos. Supongamos que $\mathbf{X}_{i}$ y $\mathbf{X}_{j}$ son dos soluciones candidatas para un problema de optimización con 20 objetivos. Si $\mathbf{X}_{i}$ es mejor que $\mathbf{X}_{j}$ en 19 objetivos, pero $\mathbf{X}_{j}$ es superior que $\mathbf{X}_{i}$ en el objetivo restante, ambas soluciones serían consideradas equivalentes si se utiliza PD para compararlas. Sin embargo, en la ausencia de preferencias entre objetivos, el tomador de decisiones podría considerar que $\mathbf{X}_{i}$ muestra claramente un mejor desempeño que $\mathbf{X}_{j}$. PD no considera la cantidad de objetivos en los que una solución es mejor que otra y omite también la magnitud de estas mejoras. Sin embargo, estos son aspectos muy importantes durante el proceso de toma de decisiones y pueden llevar a diferentes grados de dominancia \cite{Farina04,Koppen07}; descartar esta valiosa información puede llevar a errores de discriminación.

\subsection{Alternativas de solución}


En la literatura se pueden distinguir dos enfoques principales para lidiar con una alta dimensionalidad en el espacio de las funciones objetivo:

\begin{itemize}
\item \textbf{Reducción de dimensiones.}  La relación entre un par de objetivos puede ser \textit{conflictiva} (al mejorar uno de los objetivos el otro empeora), \textit{armoniosa} (al mejorar uno de los objetivos el otro también mejora)  o \textit{independiente} (el mejorar o empeorar de uno de los objetivos no tiene efecto sobre el otro) \cite{Purshouse03}, de modo que los objetivos cuya relación es armoniosa pueden ser considerados \textit{redundantes}. La reducción de dimensiones consiste en analizar las relaciones entre los diferentes objetivos de un problema con la finalidad de identificar redundancias y, de esta manera, reducir el problema al ignorar algunos objetivos innecesarios. Reducir las dimensiones claramente permite lidiar con las diferentes dificultades expuestas en la Sección \ref{sec:intromany}; sin embargo, esta reducción no siempre es posible y depende del escenario de optimización en cuestión. Algunos trabajos realizados al respecto son: \cite{Deb06e,Brockhoff06,Brockhoff07b,Brockhoff07c,Lopez08,Lopez09}

\item \textbf{Métodos alternativos de discriminación.} La mayoría de los MOEAs propuestos se basan en la dominancia de Pareto (PD) para discriminar entre soluciones y guiar el proceso de búsqueda. Sin embargo, tal como se demostró en la Sección \ref{sec:paretodrawbacks}, al incrementarse la cantidad de objetivos PD pierde su potencial discriminante provocando que el proceso de búsqueda sea llevado a cabo prácticamente de manera aleatoria. Un enfoque de solución que pareciera natural ante esta problemática es la búsqueda de métodos alternativos para discriminar entre soluciones. La idea es utilizar métodos que permitan una discriminación más estricta (de grano más fino) y robusta que la lograda a través de PD, de manera que pueda mantenerse una presión de selección adecuada para dirigir el proceso de búsqueda. Diferentes alternativas de este tipo han sido propuestas, aunque no todas con particular interés en el aumento del número de objetivos:  \cite{Bentley97,Drechsler01,Kokolo01,Farina04,Pierro07,Koppen07,Le07,Sato07a,Zou08,Giusti08}; estos y otros métodos alternativos se describen a detalle en el Capítulo \ref{chap:fitnessmethods}. 
\end{itemize}

El enfoque que seguiremos y estudiaremos en este proyecto de tesis es el segundo. 

\section{Problemas de Prueba}
\label{sec:dtlz}

Para toda la experimentación involucrada en este trabajo de tesis hemos considerado seis problemas de prueba que son parte de un conjunto de funciones específicamente propuestas para estudiar la escalabilidad de MOEAs. Estos problemas de prueba son conocidos con las siglas DTLZ, que corresponden al nombre de sus autores: Deb, Thiele, Laumanns y Zitzler \cite{Deb02a,Deb05c}. Las razones principales que motivaron la elección de estos seis problemas de prueba son las siguientes:

\begin{enumerate}
 \item Escalabilidad con respecto al número de objetivos y variables de decisión.
\item Se conoce de manera exacta la forma y localización del frente de Pareto (FP), así como los óptimos de Pareto correspondientes.
\item Existen ecuaciones que describen el FP para estos problemas, lo que permite evaluar analíticamente (sin utilizar un conjunto de referencia) la convergencia del conjunto aproximación obtenido por un MOEA.
\item Las dificultades de convergencia y diversidad pueden controlarse.
\end{enumerate}



A continuación se describen los problemas de prueba considerados para esta tesis. Para todos los casos la notación utilizada es la siguiente: el número total de variables de decisión es $n=M+k-1$, donde $M$ es el número de objetivos y $k$ es un parámetro de dificultad cuyo valor será especificado en la descripción de cada problema. $\mathbf{X}$ es un vector de variables de decisión, y $\mathbf{X}_{M}$ representará las últimas $k$ variables de $\mathbf{X}$. $x_{i}$ corresponde a la $i$-ésima variable del vector $\mathbf{X}$ y está sujeta a  $0 \leq x_{i} \leq 1$, para $i= 1, 2, \dots , n$.


\subsection{DTLZ1}
\label{sec:dtlz1}

El problema DTLZ1 se describe formalmente de la siguiente manera:
\begin{eqnarray} \label{eq:dtlz1}
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})  = \frac{1}{2}x_{1}x_{2}\dots x_{M-1}(1+g(\mathbf{X}_{M})),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})= \frac{1}{2}x_{1}x_{2}\dots (1-x_{M-1})(1+g(\mathbf{X}_{M})),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M-1}(\mathbf{X})=\frac{1}{2}x_{1}(1-x_{2})(1+g(\mathbf{X}_{M})),\\
\mbox{Minimizar} &  f_{M}(\mathbf{X})=\frac{1}{2}(1-x_{1})(1+g(\mathbf{X}_{M})),\\
\mbox{donde} & g(\mathbf{X}_{M})= 100\ [|\mathbf{X}_{M}| +  \sum_{x_{i}\in \mathbf{X}_{M}}(x_{i}-0.5)^{2} - \cos(20\pi(x_{i}-0.5)) ].
\end{array}
\right\rbrace  &
\end{eqnarray}


\begin{figure}[htp]
  \centering
\shadowbox{
\subfigure{
\includegraphics[width=8cm]{d1_1.pdf}
}
\subfigure{
\includegraphics[width=8cm]{d1_2.pdf}
}
}
\caption{Aproximación al frente de Pareto para el problema DTLZ1 con 3 objetivos.} \label{fig:d1front}
\end{figure}

Los óptimos de Pareto para este problema corresponden a $x_{i}=0.5$ para toda $x_{i} \in \mathbf{X}_{M}$. El frente de Pareto (FP) para este problema corresponde al hiperplano lineal $\sum_{m=1}^{M}f_{m}=0.5$. La figura \ref{fig:d1front} muestra una aproximación al FP para el problema DTLZ1 con tres objetivos ($M=3$). La dificultad en este problema es con respecto a la convergencia, ya que el espacio de búsqueda contiene $(11^k-1)$ atractores locales donde un MOEA puede estancarse antes de converger al FP. Para el caso de este problema se utilizará $k=5$.





\subsection{DTLZ2}
\label{sec:dtlz2}


El problema DTLZ2 tiene un FP esférico, como se muestra en la figura \ref{fig:d2front}. Este problema se define de la siguiente manera:
\begin{eqnarray} 
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \cos(\frac{x_{M-2}\pi}{2})\cos(\frac{x_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \cos(\frac{x_{M-2}\pi}{2})\sen(\frac{x_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{3}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \sen(\frac{x_{M-2}\pi}{2}),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\sen(\frac{x_{1}\pi}{2}),\\
\mbox{donde} &  g(\mathbf{X}_{M})=  \sum_{x_{i}\in \mathbf{X}_{M}}(x_{i}-0.5)^{2}.
\end{array}
\right\rbrace  &
\end{eqnarray}

Los óptimos de Pareto corresponden a $x_{i}=0.5$ para toda $x_{i} \in \mathbf{X}_{M}$. El FP para este problema es continuo, no convexo y se describe mediante la ecuación $\sum_{m=1}^{M}f_{m}^{2}=1$, que corresponde a  una hiperesfera con radio 1 y centro en el origen. El valor de $k=10$ será utilizado en este trabajo.


\begin{figure}[htp]
  \centering
\shadowbox{
\subfigure{
\includegraphics[width=8cm]{d2_1.pdf}
}
\subfigure{
\includegraphics[width=8cm]{d2_2.pdf}
}
}
\caption{Aproximación al frente de Pareto para los problemas DTLZ2-DTLZ4 con 3 objetivos.}\label{fig:d2front}
\end{figure}


\subsection{DTLZ3}
\label{sec:dtlz3}

DTLZ3 es una modificación del problema DTLZ2 descrito anteriormente. En esta versión del problema se incorporan mayores dificultades de convergencia, ya que el espacio de búsqueda incluye $(3^k-1)$ atractores locales que son paralelos al FP. La definición formal de este problema se plantea como sigue:
\begin{eqnarray} 
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \cos(\frac{x_{M-2}\pi}{2})\cos(\frac{x_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \cos(\frac{x_{M-2}\pi}{2})\sen(\frac{x_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{3}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}\pi}{2})\dots \sen(\frac{x_{M-2}\pi}{2}),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\sen(\frac{x_{1}\pi}{2}),\\
\mbox{donde} & g(\mathbf{X}_{M})= 100\ [|\mathbf{X}_{M}| +  \sum_{x_{i}\in \mathbf{X}_{M}}(x_{i}-0.5)^{2} - \cos(20\pi(x_{i}-0.5)) ].
\end{array}
\right\rbrace  &
\end{eqnarray}

Los óptimos de Pareto corresponden a $x_{i}=0.5$ para toda $x_{i} \in \mathbf{X}_{M}$. Los valores óptimos para las funciones objetivo satisfacen la ecuación $\sum_{m=1}^{M}f_{m}^{2}=1$, que corresponde a una hiperesfera con radio 1 y centro en el origen. Una aproximación al FP para esta problema con 3 objetivos puede visualizarse en la figura \ref{fig:d2front}. El valor de $k=10$ será utilizado en este trabajo.

\subsection{DTLZ4}
\label{sec:dtlz4}

El problema DTLZ2 se modificó para estudiar la habilidad de los MOEAs para mantener una buena distribución de las soluciones. DTLZ4 introduce dificultades para converger de una manera distribuida, ya que presenta un conjunto de soluciones denso en regiones específicas del espacio de búsqueda, lo que provoca la tendencia de los MOEAs a dirigir la búsqueda hacia dichas regiones. La definición formal para este problema es la siguiente:
\begin{eqnarray} 
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}^{\alpha}\pi}{2})\dots \cos(\frac{x_{M-2}^{\alpha}\pi}{2})\cos(\frac{x_{M-1}^{\alpha}\pi}{2}),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}^{\alpha}\pi}{2})\dots \cos(\frac{x_{M-2}^{\alpha}\pi}{2})\sen(\frac{x_{M-1}^{\alpha}\pi}{2}),\\
\mbox{Minimizar} &  f_{3}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{x_{1}^{\alpha}\pi}{2})\dots \sen(\frac{x_{M-2}^{\alpha}\pi}{2}),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\sen(\frac{x_{1}^{\alpha}\pi}{2}),\\
\mbox{donde} &  g(\mathbf{X}_{M})=  \sum_{x_{i}\in \mathbf{X}_{M}}(x_{i}-0.5)^{2}.
\end{array}
\right\rbrace  &
\end{eqnarray}

El FP para este problema es esférico y con las mismas características del FP descrito para los problemas DTLZ2 y DTLZ3 (ver figura \ref{fig:d2front}). Los valores de los parámetros $k=10$ y $\alpha = 100$ serán utilizados tal como se sugiere en \cite{Deb02a}. 

\begin{figure}[htp]
  \centering
\shadowbox{
\subfigure{
\includegraphics[width=8cm]{d5_1.pdf}
}
\subfigure{
\includegraphics[width=8cm]{d5_2.pdf}
}
}
\caption{Aproximación al frente de Pareto para los problemas DTLZ5 y DTLZ6 con 3 objetivos.}\label{fig:d5front}
\end{figure}

\subsection{DTLZ5}
\label{sec:dtlz5}

El problema DTLZ5 se define formalmente de la siguiente manera:
\begin{eqnarray} 
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \cos(\frac{\theta_{M-2}\pi}{2})\cos(\frac{\theta_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \cos(\frac{\theta_{M-2}\pi}{2})\sen(\frac{\theta_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{3}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \sen(\frac{\theta_{M-2}\pi}{2}),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\sen(\frac{\theta_{1}\pi}{2}),\\
\mbox{donde} &  \theta_{i} = \frac{\pi}{4(1+g(\mathbf{X}_{M}))} (1+ 2g(\mathbf{X}_{M})x_{i}),\mbox{ para }i= 1, 2, \dots , (M-1),\\
\mbox{y} &  g(\mathbf{X}_{M})=  \sum_{x_{i}\in \mathbf{X}_{M}}(x_{i}-0.5)^{2}.
\end{array}
\right\rbrace  &
\end{eqnarray}

Los óptimos para las funciones objetivo satisfacen la ecuación $\sum_{m=1}^{M}f_{m}^{2}=1$, y sus correspondientes valores en el espacio de decisión son  $x_{i}=0.5$ para toda $x_{i} \in \mathbf{X}_{M}$. El problema DTLZ5 sirve para investigar la habilidad de MOEAs para converger a una curva. La figura \ref{fig:d5front} muestra una aproximación al FP para este problema usando tres objetivos. Para este trabajo se utilizará $k=10$.




\subsection{DTLZ6}
\label{sec:dtlz6}

Al igual que el problema DTLZ5, DTLZ6 está diseñado para investigar la habilidad de MOEAs para converger a una curva (ver figura \ref{fig:d5front}). Sin embargo, DTLZ6 incorpora mayores dificultades de convergencia. Este problema se define formalmente de la siguiente manera:
\begin{eqnarray} 
&\left.
\begin{array}{rl}
\mbox{Minimizar} &  f_{1}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \cos(\frac{\theta_{M-2}\pi}{2})\cos(\frac{\theta_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{2}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \cos(\frac{\theta_{M-2}\pi}{2})\sen(\frac{\theta_{M-1}\pi}{2}),\\
\mbox{Minimizar} &  f_{3}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\cos(\frac{\theta_{1}\pi}{2})\dots \sen(\frac{\theta_{M-2}\pi}{2}),\\
\vdots & \vdots\\[-0.25cm]
\mbox{Minimizar} &  f_{M}(\mathbf{X})=  (1+g(\mathbf{X}_{M}))\sen(\frac{\theta_{1}\pi}{2}),\\
\mbox{donde} &  \theta_{i} = \frac{\pi}{4(1+g(\mathbf{X}_{M}))} (1+ 2g(\mathbf{X}_{M})x_{i}) \mbox{ para }i= 1, 2, \dots , (M-1),\\
\mbox{y} &  g(\mathbf{X}_{M})=  \sum_{x_{i}\in \mathbf{X}_{M}}x_{i}^{0.1}
\end{array}
\right\rbrace  &
\end{eqnarray}

A diferencia de los problemas descritos anteriormente, las soluciones óptimas de Pareto para DTLZ6 corresponden a $x_{i}=0$ para toda $x_{i} \in \mathbf{X}_{M}$. Los valores óptimos para las funciones objetivo satisfacen la ecuación $\sum_{m=1}^{M}f_{m}^{2}=1$. El valor de $k=|\mathbf{X}_{M}| = 10$ será utilizado en este trabajo.






\section{Métricas}
\label{sec:metricas}


\subsection{Métrica de Convergencia}
\label{sec:convergencemetric}

Deb y Jain \cite{Deb02b} propusieron en 2002 una métrica para evaluar la capacidad de convergencia de los MOEAs. Esta métrica consiste en calcular la distancia promedio entre las soluciones del conjunto aproximación $Z$ obtenido por un MOEA y el punto más cercano a cada una de ellas en el frente de Pareto, mismo que es representado mediante un conjunto de puntos de referencia $P^*$. Inicialmente se calcula para cada punto $\mathbf{X} \in Z$ la distancia Euclidiana normalizada al punto más cercano en $P^*$:
\begin{eqnarray}
\label{eq:normalizedeuclidian}
 d(\mathbf{X}) & = & \displaystyle \min_{\mathbf{X}^*\in P^*} \sqrt{\sum_{m=1}^{M}{\left(\frac{f_{m}(\mathbf{X}) - f_{m}(\mathbf{X}^{*})}{f_{m}^{max} - f_{m}^{min}}\right) ^{2}}}
\end{eqnarray}
donde $f_{m}^{max}$ y $f_{m}^{min}$ denotan respectivamente el valor máximo y mínimo para el $m$-ésimo objetivo en $P^*$. Finalmente la métrica de convergencia se calcula promediando las distancias normalizadas de las diferentes $\mathbf{X} \in Z$:
\begin{eqnarray}
\label{eq:convergencemetric}
 C(Z)& = & \frac{\sum_{\mathbf{X}\in Z}{d(\mathbf{X})}}{|Z|}
\end{eqnarray}

Para esta tesis utilizaremos una variante de la métrica de convergencia de Deb y Jain \cite{Deb02b} previamente descrita. Dado que para los seis problemas de prueba considerados se conocen ecuaciones que describen el FP, el valor de $d(\mathbf{X})$ para cada $\mathbf{X} \in Z$ se determinó analíticamente (sin utilizar un conjunto de referencia) \cite{Khare03,Wagner07}. 

% Para DTLZ1 el FP corresponde al hiperplano lineal descrito por la ecuación $\sum_{m=1}^{M}{f_{m}}  =  0.5$, de tal modo que es posible obtener la mínima distancia de un punto determinado a dicho hiperplano utilizando expresiones algebraicas conocidas. Por otro lado, el FP para los problemas DTLZ2-DTLZ6 está descrito por la ecuación $\sum_{m=1}^{M}{f_{m}^{2}}  = 1$, que corresponde a la ecuación de una hiperesfera con radio 1 y centro en el origen de un espacio Euclidiano de $M$ dimensiones. 

Por otra parte, el conjunto aproximación $Z$ puede incluir a la vez soluciones buenas (cercanas al PF) y malas (lejanas al PF), aún cuando son no dominadas con respecto a la dominancia de Pareto (situación especialmente común al optimizar muchos objetivos). De este modo, la distancia promedio puede estar influenciada por las malas soluciones, pudiendo opacar en algunos casos la habilidad de un determinado MOEA para encontrar soluciones que presenten una buena convergencia. Por estos motivos, en lugar de calcular la distancia promedio se utilizará como medida de convergencia la distancia entre la mejor solución encontrada (solución con mejor convergencia) y el FP de los diferentes problemas de prueba:
\begin{eqnarray}
\label{eq:convergencemetric}
 C(Z)& = & \min_{\mathbf{X}\in Z}{d(\mathbf{X})}
\end{eqnarray}


Mientras más pequeño sea el valor para esta métrica, mejor será el desempeño del algoritmo evaluado.





\subsection{Distancia Generacional Invertida}
\label{sec:igdmetric}


La \textit{distancia generacional} (DG) es una métrica propuesta por Van Veldhuizen en 1999 \cite{Veldhuizen99a}. DG consiste en calcular la distancia promedio de un conjunto de soluciones candidatas $Z$, con respecto a un conjunto de referencia $P^{*}$ que representa al frente de Pareto (FP). Formalmente, DG se define por la Ecuación \ref{eq:gd}:
\begin{eqnarray}
\label{eq:gd}
 DG & = & \frac{\sqrt{\sum_{\mathbf{X} \in Z}d(\mathbf{X})^{2}}}{|Z|}
\end{eqnarray}
donde $d(\mathbf{X})$ es la distancia Euclidiana entre la solución $\mathbf{X}$ y el punto en $P^{*}$ más cercano a ella:
\begin{eqnarray}
\label{eq:gd2}
 d(\mathbf{X}) & = & \min_{\mathbf{X}^{*} \in P^{*}}\sqrt{ \sum_{m=1}^{M}{(f_{m}(\mathbf{X}) - f_{m}(\mathbf{X}^{*}))^{2}}}
\end{eqnarray}

Aunque DG es una métrica para evaluar convergencia, si invertimos los papeles de $Z$ y $P^{*}$ en las Ecuaciones (\ref{eq:gd}) y (\ref{eq:gd2}), lo que se conoce como \textit{distancia generacional invertida} (DGI), es posible tomar en cuenta también la diversidad del conjunto $Z$. De esta manera, un valor bajo para DGI indicará tanto una buena convergencia como buena distribución de las soluciones. De manera formal, la métrica DGI se define como sigue:
\begin{eqnarray}
\label{eq:gd}
 DGI & = & \frac{\sqrt{\sum_{\mathbf{X}^{*} \in P^{*}}d(\mathbf{X}^{*})^{2}}}{|P^{*}|}
\end{eqnarray}
donde $d(\mathbf{X}^{*})$ es la distancia Euclidiana entre el punto de referencia $\mathbf{X}^{*}$ y la solución en $Z$ más cercana:
\begin{eqnarray}
\label{eq:gd2}
d(\mathbf{X}^{*}) & = & \min_{\mathbf{X} \in Z}\sqrt{ \sum_{m=1}^{M}{(f_{m}(\mathbf{X}) - f_{m}(\mathbf{X}^{*}))^{2}}}
\end{eqnarray}



Para este trabajo el conjunto $P^{*}$ estará formado únicamente por los extremos del FP y el punto conocido como la \textit{rodilla} (\textit{knee}) del FP \cite{Lopez09d}; la rodilla es el punto del FP que presenta el mejor compromiso entre los diferentes objetivos del problema, en el que podría asumirse que el tomador de decisiones estará interesado. Para el problema DTLZ1 los extremos del FP están dados por los $M$ vectores $\mathbf{F}_i = [f_{1}^i, f_{2}^i, \dots , f_{M}^i]$ tales que se cumpla que $f_{m}^i=0.5$ si $m=i$ y $f_{m}^i=0$, en caso contrario, para $i \in \{1, 2, \dots , M\}$ (donde $M$ es la cantidad de objetivos), mientras que la rodilla para este problema corresponde al punto r = $\frac{0.5}{M}^M$. Por otra parte, para los problemas DTLZ2-DTLZ6 los extremos del FP están dados por los $M$ vectores $\mathbf{F}_i = [f_{1}^i, f_{2}^i, \dots , f_{M}^i]$ tales que se cumpla que $f_{m}^i=1.0$ si $m=i$ y $f_{m}^i=0$ en caso contrario, para $i \in \{1, 2, \dots , M\}$. La rodilla en el caso de los problemas DTLZ2-DTLZ6 corresponde al punto r = $\frac{1}{\sqrt{M}}^M$. 

De este modo, el conjunto $P^{*}$ utilizado para calcular la métrica DGI contiene en todos los casos únicamente $M+1$ puntos de referencia. Para dejar claro este punto consideremos el caso de los problemas DTLZ2-DTLZ6 con 5 objetivos. El conjunto de referencia $P^*$ utilizado para calcular la métrica DGI es: 

$P^*=\{[0,0,0,0,1], [0,0,0,1,0], [0,0,1,0,0], [0,1,0,0,0], [1,0,0,0,0],[\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}}]\} $\\

% \clearpage

La ubicación de las soluciones encontradas por un MOEA puede favorecer o no el resultado de la métrica DGI. Por ejemplo, si un algoritmo A logra encontrar uno de los extremos del FP para determinado problema, mientras que otro algoritmo B converge exactamente a la rodilla, claramente el B logrará un mejor valor para la métrica, pues la rodilla es el punto más cercano a los diferentes puntos de referencia incluidos en $P^*$.


